#include <vector>
using namespace std;
#include <set>
#include <algorithm>


// version 1 
class Solution {
public:
    int mySqrt(int x) {
        //每次都从最大数字开始找 -> 没有必要
        //最好是从靠近x的平方根开始找！
        int left = 0, right = 0;
        //调整一下right的起始位置
        right = (x > 65536) ? 65536 : x;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            long long sqr = (long long)mid * mid;
            if(sqr > x) right = --mid;
            else left = mid; 
        }
        return left;
    }
};